package main

import "fmt"

func countBits(n int) []int {
	ans := make([]int, n+2)
	for i := 0; i <= n; i++ {
		//10进制转2进制,再统计1的数量
		num := i
		count := 0
		for num > 0 {
			if num%2 == 1 {
				count++
			}
			num /= 2
		}
		ans[i] = count
	}
	return ans
}
func countBitsDp(n int) []int {
	//ans[i] i的二进制位1的数量
	ans := make([]int, n+2)
	ans[0] = 0
	if n == 0 {
		return ans
	}
	ans[1] = 1
	for i := 0; i <= n; i++ {
		// i 为偶数
		if i%2 == 0 {
			ans[i] = ans[i/2]
		} else {
			ans[i] = ans[i-1] + 1
		}
	}
	return ans
}

func main() {
	fmt.Println(countBitsDp(0))
}
